import java.util.*;
class Bank {
    long[] balance;
    int len;
    public Bank(long[] balance) {
        this.balance=balance;
        len=balance.length;
    }

    public boolean transfer(int account1, int account2, long money) {
        int x=account1-1;
        int y=account2-1;
        if(x>=0&&x<len&&y>=0&&y<len&&balance[x]>=money){
            balance[x]-=money;
            balance[y]+=money;
            return true;
        }
        return false;
    }

    public boolean deposit(int account, long money) {
        int index=account-1;
        if(index>=0&&index<len){
            balance[index]+=money;
            return true;
        }
        return false;
    }

    public boolean withdraw(int account, long money) {
        int index=account-1;
        if(index>=0&&index<len&&balance[index]>=money){
            balance[index]-=money;
            return true;
        }
        return false;
    }
}
public class project {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int sum=0;
        for(int i=0;i< customers.length;i++){
            if(grumpy[i]==0){
                sum+=customers[i];
                customers[i]=0;
            }
        }
        int max=0;
        int tmp=0;
        for(int i=0;i<customers.length;i++){
            tmp+=customers[i];
            if(i>=minutes){
                tmp-=customers[i-minutes];
            }
            max=Math.max(tmp,max);
        }
        return sum+max;
    }




















    public int mostFrequent(int[] nums, int key) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(nums[i]==key&&i<nums.length-1){
                map.put(nums[i+1],map.getOrDefault(nums[i+1],0)+1);
            }
        }
        int maxCount=0;
        int value=0;
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            if(entry.getValue()>maxCount){
                maxCount=entry.getValue();
                value=entry.getKey();
            }
        }
        return value;
    }















    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs,(a,b)->a[1]-b[1]);
        int ret=0;
        int value=Integer.MIN_VALUE;
        for(int i=0;i<pairs.length;i++){
            if(value<pairs[i][0]){
                value=pairs[i][1];
                ret++;
            }
        }
        return ret;
    }



















    public int nthUglyNumber(int n) {
        int[] dp=new int[n+1];
        int p2=1;
        int p3=1;
        int p5=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            int sum2=dp[p2]*2;
            int sum3=dp[p3]*3;
            int sum5=dp[p5]*5;
            dp[i]=Math.min(sum2,Math.min(sum3,sum5));
            if(dp[i]==sum2){
                p2++;
            }
            if(dp[i]==sum3){
                p3++;
            }
            if(dp[i]==sum5){
                p5++;
            }
        }
        return dp[n];
    }






















    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while (scanner.hasNext()){
            String str1=scanner.nextLine();
            String str2=scanner.nextLine();
            int len1=str1.length();
            int len2= str2.length();
            int[][] dp=new int[len1+1][len2+1];
            for(int i=1;i<=len1;i++){
                dp[i][0]=i;
            }
            for(int i=1;i<=len2;i++){
                dp[0][i]=i;
            }
            for(int i=1;i<=len1;i++){
                for(int j=1;j<=len2;j++){
                    if(str1.charAt(i-1)==str2.charAt(j-1)){
                        dp[i][j]=dp[i-1][j-1];
                    }else{
                        dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]));
                    }
                }
            }
            System.out.println(dp[len1][len2]);
        }
    }















    public int getValue(int[] gifts, int n) {
        // write code here
        Arrays.sort(gifts);
        int value=gifts[n/2];
        int count=0;
        for(int i=0;i<n;i++){
            if(value==gifts[i]){
                count++;
            }
        }
        return count<=n/2?0:value;
    }
}
